There exist systems for accomplishing automatic authentication or identification of a person using his/her fingerprint. A fingerprint of a person comprises a distinctive and unique ridge pattern structure. For authentication or identification purposes, this ridge pattern structure can be characterized by endings and bifurcations of the individual ridges. These features are popularly known as minutiae.
An example of portion of a fingerprint is shown in FIG. 1A. The minutiae for the portion of the fingerprint shown in FIG. 1A are shown in FIG. 1B as being enclosed by "boxes." For example, box 101B shows a bifurcation minutiae of a bifurcated ridge 10A and box 103B shows a ridge ending minutiae of ridge 103A. Note that minutiae on the ridges in fingerprints have directions (also called orientations) 105 associated with them. The direction 113B of a minutiae at a ridge end 103B is the direction in which the end of the ridge points. The direction 111B of a bifurcation minutiae 101B is the direction in which the bifurcated ridge points. Minutiae also have locations which are the positions, with respect to some coordinate system, of the minutiae on the fingerprint.
FIG. 2 is a flow chart showing the steps generally performed by a typical prior art system 200.
In step 210, the image is acquired. This acquisition of the image could either be through a CCD camera and framegrabber interface or through a document scanner communicating with the primary computing equipment.
Once the image is acquired into the computer memory or onto disk, relevant minutia features are extracted (220). Not all of the features thus extracted are reliable; some of the unreliable features are optionally edited or pruned (step 230), e.g. manually. The resultant reliable features are used for matching the fingers (step 240).
The fingerprint feature extraction 220, pruning 230, and matching system 240 constitute the primary backbone 250 of a typical minutiae-based automatic fingerprint identification systems (AFIS). The matching results are could be verified by a human expert or by an automatic process (step 260). The verification may also be performed automatically. The following reference describes examples of the state of the prior art for feature extraction:
Nalini K. Ratha and Shaoyun Chen and Anil K. Jain, PA1 Adaptive flow orientation based feature extraction in fingerprint PA1 images, Journal of Pattern Recognition, PA1 vol. 28, no. 11, pp. 1657-1672, November, 1995.
This reference is herein incorporated by reference in its entirety.
FIG. 3A is a flow chart showing the prior art steps performed by a feature extraction process 220 that are similar to some of the feature extraction methods proposed by Ratha, Jain, and Chen in the article referenced above.
It is often not desirable to directly use the input fingerprint image for feature extraction. The fingerprint image might need an enhancement or preprocessing before one could further extract minutiae. Typically, a smoothing process is employed to reduce the pixel-wise noise (step 305).
After the preprocessing stages, prior art systems find the directions of the ridge flow (step 310). The next important step in the processing is finding the exact location of the finger in the image. To accomplish this a process referred to as the foreground/background segmentation (step 315) separates the finger part of the image from the background part of the image. Once the finger part is localized, i.e., segmented to define its location, the next step is to extract the ridges from the finger image (step 320). The ridges thus extracted are thick and might contain some noisy artifacts which do not correspond to any meaningful structures on the finger. These small structures, i.e., the noisy artifacts, can be safely removed and the longer structures are smoothed (step 325). The longer structures are thinned to one-pixel width and then processed to remove any other artifacts using morphological operators (step 330). The locations and orientations of ridge endings and bifurcations are then extracted from the thinned structures (step 335) to obtain the minutiae. In some systems, a "cleanup" or post processing 340 is performed. Here undesirable minutiae are removed based on some criteria.
One of the prevalent methods of fingerprint authentication and identification methods is based on minutiae features. These systems need to process the fingerprint images to obtain accurate and reliable minutiae features to effectively determine the identity of a person.
The following reference describes examples of the state of the prior art fingerprint matcher:
N. Ratha, K. Karu, S. Chen and A. K. Jain, A Real-time Matching System for Large Fingerprint Database, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 18, Number 8, pages 799-813, 1996.
This reference is herein incorporated by reference in its entirety.
Given two (input and template) sets of features originating from two fingerprints, the objective of the feature matching system is to determine whether or not the prints represent the same finger. FIG. 3B is a flow chart showing the prior art steps performed by a feature matching system 240 that is similar to the feature matching system proposed by Ratha, Karu, Chen, and Jain in the article incorporated above.
A minutia in the input fingerprint and a minutiae in the template fingerprint are said to be corresponding if they represent the identical minutiae scanned from the same finger. An alignment estimation method based on Generalized Hough Transform estimates the parameters of the overall rotation, scaling and translation between the features of the input and template fingerprint (350). In step 360 the input fingerprint features are aligned with the template fingerprint using the rotation, translation, and scaling parameters estimated in step 350. In step 370, the aligned features of the input fingerprint features are matched with the features of the template fingerprint features. The matching consists of counting the number of features in the aligned input fingerprint representation for which there exists a corresponding consistent feature in the template fingerprint representation. The verification of a corresponding feature is performed as follows: for each feature in the aligned input fingerprint feature, the matcher determines whether there is a consistent template fingerprint feature in its rectangular neighborhood whose size is predetermined. Normalizer 380 takes the raw score generated by the matcher and computes a normalized score. The higher the normalized score, the higher the likelihood that the test and template fingerprints are the scans of the same finger.
A number of terms will be defined at the outset.
Pixels in an image could be organized in rows and columns. A pixel location in image is determined by the row and column number of that pixel in the image.
Orientation/direction attribute of a pixel in an image could refer to the direction of any number of physical events associated with that pixel. In some circumstances, it could mean the direction of image brightness gradient. In a sequence of images in a video, it could refer to the direction of movement of a pixel from one image frame to the next. In this disclosure, we are interested in the direction of image brightness gradient in general. In this description, a preferred image is a fingerprint image and these images will be described as an example embodiment of the invention without loss of generality. As describe below, other implementations of the invention are envisioned. One orientation at a pixel is referred to in this document, is the direction of the fingerprint ridge flow at the pixel in a fingerprint image.
A pixel neighborhood function of a given pixel identifies which pixels spatially adjacent to that pixel could be considered as its neighbors.
A block is contiguous connected region, typically bounded by a polygon, in an image. Block size of a block is determined by the area of the block and typically defined in terms of number of pixels.
A block neighborhood function of a given block identifies which blocks spatially adjacent to that block could be considered as its neighbors.
A block direction refers to the direction which can represent the directions of all/most of the pixels in the given block.
The orientation field of a fingerprint image represents the intrinsic nature of the fingerprint image. It plays a very important role in fingerprint image analysis. A number of methods have been proposed to estimate the orientation field of fingerprint images as disclosed in the references cited below which are herein incorporated by reference in their entirety:
Kawagoe and A. Tojo, Fingerprint Pattern Classification, Pattern Recognition, Vol. 17, No. 3, pp. 295-303, 1984.
A. R. Rao and R. C. Jain, Computerized Flow Field Analysis: Oriented Texture Fields, Transactions of Pattern Analysis and Machine Intelligence, July, 1992, Vol. 14, No. 7, pages 693-709.
B. M. Mehtre, N. N. Murthy, S. Kapoor, and B. Chatterjee, Segmentation of Fingerprint Images Using the Directional Image, Pattern Recognition, Vol. 20, No. 4, pp. 429-435, 1987.
M. Kass and A. Witkin, Analyzing Oriented Patterns, Computer Vision, Graphics and Image Processing, Vol. 37, No. 4, pp. 362-385, 1987.